Circuit Labs - Electronic Circuits Collection

Cryptography is usually thought of as concerned only with keeping secrets, but there is another use for cryptography, which has more to do with keeping things in the open. This other use, which rightly belongs in this issue on All Things Security, is data authentication: techniques for verifying that data has not been tampered with.

Where financial decisions depend on recorded data, there is an incentive to falsify it. Falsification of data may disguise an embarrassing oversight or just make a report more readable; it may gain a lucrative contract or hide a fatal error. Keeping data secret is a poor choice, as it may be needed to make day to day or even minute by minute decision in the field. The device presented in this article is a data authenticator. It takes data which has been gathered by a data logger and checks an authentication code which was generated by the logger in order to verify that the data has not been changed. A typical system that would benefit from data authentication is shown in Figure 1. Changing or moving a single character will give a different code, which can not be generated without knowing a keycode that is inaccessibly hidden on the logger and the authenticator. The authenticator is called “Colossus Jr.” in honour of Tommy Flowers and the others at Dollis Hill GPO Research Labs who during WW2 built an early digital computer of that name to crack the Nazi cryptographic codes used on, among others, Lorenz cipher machines (including several versions of the Enigma).

60+ years on… PIC time!

To build our Colossus Jr., it wasn’t necessary to use a large or powerful microcontroller: there are only two outputs and one input, while the code fits into less than 1000 words of program. The only consideration that is not found in the basement level microcontrollers is that an interrupt was needed in order to allow it to read more data while chewing over the last batch. The Microchip PIC12F675 was chosen for this task as it can run at the needed speed while drawing no more current than the DTR terminal on a standard RS232 can afford. Nor are the parts costly or hard to come by — apart from the supporting chips used, just three transistors and a few passive components.

psst….DES encryption

 
The encryption routines and the actual data authentication implemented in Colossus Jr. are in accordance with the United States National Bureau of Standards Data Encryption Standard, DES. These were written in the late 1970s, partly with the assistance of the spooks of the National Security Agency. The details of how DES works have been a closely guarded secret until recently. I could have told you how they work — but then..... In sharp contrast to the previous secrecy, the details of their operation are now available on the web, not least on the National Bureau of Standards as Federal Information Processing Standards Publications FIPS PUB 46-3. Although the DES code can be cracked for encryption if you have large enough “known” and “encrypted” versions of the same data, lots of time and a Very Big Computer, the same doesn’t apply to data authentication. Finding a key which works for the data set may be possible but it will only be 1 of 224 (16,777,216) keys which work for that set of data, out of 256 or a whopping 72,057,594,037,927,936 possible keys. Finding one key that works for the original data does not mean it can be used to validate changed data. For a description of the convolutions used in the encryption engine and for the use of this in data authorization we will leave you to the references at the end of this article. A good in-depth description of the operation of the DES is found in [1], ‘The DES Algorithm Illustrated’ by J. Orlin Grabbe.

A mini Colossus

a microcontroller without on-silicon serial support can still communicate at high speed through ‘bit-bang’ techniques

The encryption engine code in the authenticator adheres fairly rigorously to the DES standard (see inset). We say ‘fairly’ because one of the tables, known as ‘Permuted Choice 1’ can be omitted, although the convolutions performed by this will still need to be done, they
can be done externally on the original 56-bit key code to generate an internal 64-bit key. The extension of the DES for purposes of data authentication is covered in FIPS PUB 113, the algorithm is known as the Digital Authentication Algorithm, or DAA Each input block is Exclusive-ORed (XORed) with the output of the last block, the result of this being sent through the DES encryption engine to give rise to the next output block. The last input block is padded if necessary with null characters (Hex 00) to fill the block and the Data Authentication Code (DAC) is selected from the most significant bits of the final output block.

Our implementation of the DAA differs from FIPS PUB 113 only in that the 0’th output is a string of eight null characters and the initial data block is XORed with that. This is functionally identical with FIPS 113, but is done to make for a more symmetrical subroutine. The final selection of bits to make up the Data Authentication Code (DAC) is the most significant 32 bits of the final block (see the example in Figure 2). Practical circuit and use The circuit diagram of Colossus Jr. shown in Figure 3 is a far cry from the heavily classified
‘blueprints’ of its famous ancestor originally designed more than 60 years ago, weighing tonnes and built from relays and thermionic valves. By the way, did you know Colossus has been rebuilt by volunteers and can be seen working at Bletchley Park Museum? See reference [5]. Today, we’re dealing with an 8-pin PIC microcontroller weighing next to nothing in just another black-box configuration, i.e., minimum hardware, maximum software.

Figure 1. Example of a system that would benefit from data authentication as files are being transferred at least three times between equipment.

The PIC employs its on-board oscillator in combination with an 8-MHz ceramic resonator, RES1. The circuit supply voltage is stolen, via a 7805 regulator, from the DTR line of the PC’s
RS232 port. The inactive level of DTR (Windows default) is logic ‘0’ or a level between about +10 V and +12 V. In operation the device is connected to an RS232 serial port on a computer via K1 and the file to be verified is sent to the authenticator. A stop character will acknowledge each block of eight characters received on the PIC unless they have a parity error or a framing error responded to by a ‘P’ or ‘F’ respectively. The end of the data file must be marked by an ESC (‘escape’) character, after which the authentication code must be sent. This is eight hex digits, 0-9 and A-F that represent a 4-byte code. The circuit will respond to the code with either ‘Verified’ or ‘Rejected’ depending on the match.

Building it…

… should also differ vastly from the colossal effort that went into constructing the original deciphering machine during WW2. Figure 4 shows the tiny PCB designed for the Colossus
Junior. Construction is straightforward as no special parts or techniques are used. The 7805 voltage regulator, IC2, can make do without a heatsink. The PIC programming interface is a 5-way single-in-line pinheader; the PC interface, a 9-way sub-D socket for PCB edge mounting. The PIC micro is seated in an 8-way DIL socket. Connect Colossus Jr. to the serial port on your PC by way of a non-crossed RS232 cable. The communication program on the PC (like HyperTerminal) should be set to 9600 baud, even parity, 8 data bits, 1 stop bit (9600,E,8,1).

Customizing your Colossus Jr. 

You will have to think up your own ‘private key’ and insert it into the software. To do this you will need to open and edit the PIC source code file as detailed below using the well-known MPLAB utility from Microchip (free download from www.microchip.com). The circuit is capable of either adding a signature to a data file, or check if a certain file has been changed using this signature. You, the user, select between these two functions. Now, follow these steps:

* Key customizing
Open the file ‘des.mcp’ using MPLAB. You will probably get two error reports which can safely be ignored, so just click on ‘OK’. To be able to modify the source code you’ll need to open the files ‘p1.inc’ and ‘des.asm’ (see also inset). Authorize/Verify selection Selectt the function of Colossus Jr. in lines 17 and 18 of the file ‘des.asm’. For the Authorize (file transmit) function a signature is added by this text:
#define Authorize
; #define Validate
The other function, data authentication
(file reception) is selected by commenting
out line 17, so:
; #define Authorize
#define Validate

* Changing the key
You can find the key in lines 15 and 16 of the ‘p1.inc’ file. Initially this will read
PassKeyL = 0x13345779
PassKeyR = 0x9BBCDFF1
so the actual key used is: 133457799BBCDFF1
The key needs to be split like this because it’s the only way MPLAB can handle 32-bit values.

* Compiling and programming
Once the files have been edited to your requirements, you are ready to create a programmer file. In the MPLAB menu, pick ‘Project’ from the menu and then click on ‘Build’. An object code file called ‘des.hex’ will be created in the A PIC programmer supporting the 12F675 is required to transfer the object code file to the actual 8-pin chip. The circuit has a SIL pinheader, K2, containing all signals required for incircuit (!) programming of the PIC. More on the microcontroller software The microcontroller code being available as a free download from our website (040267-11.zip), you have a great opportunity to learn a bit (pun intended) about cryptography and data authentication at PIC assembly code level — excellent reading for a rainy afternoon! The code is divided into three parts, the operating core which receives data and authentication codes, the interrupt service routine which allows data to be received in the background while the microcontroller is working on previously received data, and the encryption engine which takes blocks of data and converts them into an encrypted version.

The serial input and output routines are what is known as ‘bit-bangers’ in that they don’t need any supporting silicon on the microcontroller but use direct manipulation of general purpose input and output ports. The input routine is interrupt driven and is designed to receive data in the background, much if not all of the encryption can be done in the time that it takes to read a batch of eight characters. Output is also interrupt driven, but works in the foreground as little data has to be output; only the block acknowledgements and the “Verified” or “Rejected” messages. (040267-1)

• The Windows XP FIFO Buffer

With Colossus Jr. connected to a Windows XP PC you’ll find that the RTS/CTS handshaking on the RS232 port will not work very well in combination with the FIFO buffer activity. For proper handshaking with Colossus Jr. this activity has to be minimised or, even better, turned off completely. Here’s how to do it. From the Start button, select Control Panels, then System → Hardware → Device Manager → Ports. Right-click on the serial port concerned (e.g., COM1), then select Port Settings. Click on the Advanced button and in the window that opens, uncheck ‘Use FIFO buffers’ to disable the buffer function altogether.

Figure 3. Circuit diagram of Colossus Jr.: a PIC with some I/O hardware strewn around it. Note that the circuit is powered off the PC’s (inactive) DTR line, which is normally at about +10 V.

• COMPONENTS LIST
  

  Resistors: R1,R4,R6,R7 = 22kΩ R2 = 10kΩ R3,R5 = 2kΩ2 R8 = 270ø	Capacitors: C1 = 100nF C2 = 22μF 16V radial C3,C4 = 10μF 16V radial	Semiconductors: D1 = 1N4148 T1,T2 = BC557B T3 = BC547B IC1 = PIC12F675-C/P, programmed. Publishers order code 040267- 41* IC2 = 7805CP
  Miscellaneous: K1 = 9-way sub-D socket (female), PCB edge mounting K2 = 5-way SIL pinheader Res1 = 8.000MHz ceramic resonator 8-way IC socket RS232 serial cable (non-crossed)		PCB, ref. 040267-1 from The PCBShop Disk, PIC source code files, order code 040267-11* or Free Download * see Elektor SHOP page or www.elektor-electronics.co.uk

Figure 4. PCB copper track layout and component mounting plan.

Check & double-check: the DES routine

resonator and a serial bit rate of
; 9600bps. Although only 7 bits of data are used, the byte size is 8 bits with an
; additional parity bit - the parity is even.
#include “P12F675.inc” ; Microchip supplied defs
#include “des675.inc”
; This file does a convolution of the cryptographic key using the MPLAB assemblers itself
; to replace the “Permuted Choice 1” convolution.
;
; * * * ***** EDIT THIS FILE TO CHANGE THE KEY ***** * * *
;
; Note that the listing of this file has been switched off to reduce clutter.
#include “PC1.INC”
org 0000
goto init
org 0004
#include “intser.asm”
; Table contains the key in the first 8 bytes, it additionally has status and
; judgement strings.
Table addwf PCL,F
nop
DT PC1_0, PC1_1, PC1_2, PC1_3, PC1_4, PC1_5, PC1_6, PC1_7
Verify DT “Pass”, 0
Reject DT “Fail”, 0
Ready DT “Ready”, 0
init bsf STATUS,RP0
movlw b’11111100’ ; bit 0 is busy, 1 is tx data
movwf TRISIO
clrf ANSEL
bcf STATUS,RP0
movlw 7
movwf CMCON ; switch off comparators

(Elektor Electronics Magazine - 10/2005)