From: secedu@all.net
Reply-to: secedu@all.net
Organization: Information Security Educators Mailing List
Subject: Information Security Educators Mailing List 1998-10-07
<pre>---------------------------------------------
Date: Wed, 07 Oct 1998 08:51:45 +0100 (BST)
From: Paul Orlowski <paul.orlowski@gecm.com>
Subject: Re: Information Security Educators Mailing List 1998-10-05


Interesting problem.  My expertise is in ANSI C, particularly on embedded
platforms.  However, not having access to a C compiler in my current role, I
will outline what I would look for in a good, defensively written program.

Assume the following for simplicity:

Nos are integers.

Nos are delivered in some form which are provided to the program by some
function

Int get_next_num(void);


<Start analysis>


Point 1:

good programming practice to define a cap on the maximum number of numbers
which can be processed by the program like:

#define MAX_NUMBERS 1000 // 1000 number capacity.
Also
#define TRUE 1
#define FALSE (!TRUE)

Point 2:

Define a static area of storage, nice and big which can take the sum, and
initialise it to 0 at program invocation.  The shrewder of our congregation
will also place guard variables either side of this variable ( depending on
OS).  These guard variables should be initialised to values of impulsive
autocorrelation function, which have a low probability of appearing in normal
data.  MPT 1327 uses 0xC4D7 which has proved useful during my dabblings with
many systems. I have also used 127 bit Gold Codes for this purpose.

Also note the use of static vars for reliability.  Most C compilers prohibit
the altering of these vars by other modules in the system.

i.e.

static pre_guard_byte = 0xC4D7 ;
static unsigned long master_sum = 0L;
static post_guard_byte = 0xC4D7 ;

Point 3:

Define and maintain an unsigned long count of the numbers processed.

Unsigned long no_nos_processed = 0L ;

Point 4:
Install a fatal error handler as follows (OS dependant)

Int err_hand(int whatever)
{
if (validate_sum()== TRUE)=09=09// always good practice to compare with a value
// rather than leave it to the compiler to cast !!
printf("%lu\n",master_sum);
 return(whatever)
}
This will still print the sum if it has been calculated correctly in =
the event
of a catastrophic error.  I concede that you might not want to do thi=
s,
depending on how secure your definition of secure is.  The function
validate_sum checks that:

1. the guard bytes are still in tact around our sum.
2. No addition overflow has occurred
3. We have not exceeded the maximum number of numbers we can handle
4. (Optional) can also call a function which calculates the sum in a different
way ( e.g. backwards) and compares it with the sum we are just about to print.


Point 5

The main loop would look summat like;


Void main (void)
{


 // depending on the security criticality of the program, might like to
put guard variables around this bit.
 unsigned char overflowed = FALSE;
 unsigned long index = 0;
 unsigned long scratch ;

 while (index < MAX_NUMBERS)
 {

  scratch = 0L;
  scratch = get_next_num();

  // test for overflow with a statement like
  if( (sum +scratch)>sum)
  {
   // not about to overflow, so add the numbers
   sum += scratch ;
  }
  else
  {
   // about to overflow so trap it, assert overflow flag,
and plop out of loop
   // there are more elegant ways of achieving this latter
bit!
   overflowed = TRUE ;
   // NOTE overflowed will be checked by our validation
function before print
   index = MAX_NUMBERS ;
  }
  index++;
 }

 // now duplicate the bit of code in our error handler which output=
s the
number:

 if (validate_sum()==TURE)
  printf("%lu\n",master_sum);

exit(0);   // DOS like return
return ;   // for compliance with ANSI  
}

Point 6:

For the really paranoid, one might try sprinteffing the sum to a test char
buffer and testing the result to note of the output will work.  It should be
noted that the value of testing the return values of printf, sprintf vsprintf
etc should be treated with care.

Point 7:
Please forgive any syntax errors, as I don't have a C compiler to hand.  I
think I have illustrated the principles though.  Also, Word has capitalised
various bits which it should not.

Point 8:
Code considered too small to implement a full layer of error handling, although
this would be in order on larger systems.

Point 9:
The question alludes to data separation of source numbers and the resultant
sum.  Most of the countermeasures contributing to this would be hardware
specific - depending on the processor.  A full discussion would take pages !!

Point 10:
Beware of compiler optimisations - its always worth examining the assembler the
compiler generates!
---------------------------------------------
Subject: adder version 0.2
Date: Wed, 07 Oct 98 16:27:36 -0700
From: "Eli Dart" <eddart@california.sandia.gov>

/*	This is my attempt at a secure adder.  

	Eli Dart
	October 1998
	Version 0.2 



	Notes:

		1) Input comes in as a character stream on stdin.  
		Strings of numbers come in least significant digit first.

		2) Output is written to stdout, most significant digit
		first.

		3) Non-numeric characters will be treated as delimiters.
		Any non-numeric character in the input stream will signal
		the end of the current number, and subsequent non-numeric
		characters will be ignored until a numeric character is
		received.

		4) No fair sending this process signals to interrupt it.

		5) The sum of the numbers shall not be more than
		10^8388608 - 1.

	Changes:
		Version 0.2:	Add random length CPU cycle sink so that 
				the running time of the process does not
				convey information about the length of
				the input stream.  Amount of sink and
				number of calls to the sink are randomly
				chosen with each run.

*/



#include <stdio.h>
#include <malloc.h>	/* for size_t type */
#include <time.h>	/* for time functions */
#include <stdlib.h>	/* for random number generator */


/* globals */
char*	buffer;			/* big hairy buffer containing the sum */
char	byte;			/* buffer for use with read() */
size_t	bytesRead = 1;		/* the number of bytes read() reads from stdin */
size_t	numBytes = 8388608;	/* number of bytes in sum buffer */
char	zero = 0;
size_t	index;			/* index into buffer */
char	sum;			/* sum of one byte and one character from buffer */
char	carry;			/* carry to next addition */
unsigned long	randInt;		/* for CPU cycle sink -- how many */
unsigned long	smackMe;		/* this int gets smacked around a lot */
int	howOften;		/* how often we burn time */


/*	Function isNumber -- takes a character as an argument, and 
	returns 1 if the character is one of 0,1,2,3,4,5,6,7,8 or 9.
	If the character is not one of these, 0 is returned. This
	assumes the ASCII character set.
*/
int isNumber (char arg) {
	if ( (arg >= 48) && (arg <= 57) ) return 1;
	else return 0;
}




/*	Function readWhiteSpace -- reads non-numeric characters from
	stdin and throws them away.  Returns 1 if there is a valid
	numberic character in "byte", returns 0 if read() returns 0
	(signifying EOF).
*/
int readWhiteSpace() {
	bytesRead = read(0, &byte, 1);
	while (bytesRead) {
		if ( isNumber(byte) ) return 1;
		bytesRead = read(0, &byte, 1);
	}
	return 0;	/* if we get here, we're at eof */
} 



/*	Function cleanup() -- after we are no longer getting
	more numbers on stdin, we need to make sure we have
	propagated the carry all the way through.  This is 
	what cleanup() does.
*/
void cleanup() {

	while (carry > 0) {
		sum = buffer[index] + carry;
		carry = sum / 10;
		sum = sum % 10;
		buffer[index] = sum;
		--index;
	}
	return;
}




/*	Function addNumber() -- adds a number coming into stdin
	to the sum in buffer.  Returns 0 if stdin is at eof, 1
	otherwise.  Assumes that the character in byte is numeric
	as defined by isNumber(), above.
*/
int addNumber() {
	index = numBytes - 1;
	sum = 0;
	carry = 0;

	/* do the least significant place (requires no carry) */
	sum = buffer[index] + (byte - 48);
	carry = sum / 10;
	sum = sum % 10;
	buffer[index] = sum;
	--index;

	/* do the rest of the number */
	while ( (bytesRead = read(0, &byte, 1)) > 0 ) {
		if ( !isNumber(byte) ) {
			cleanup();
			return 1;
		}
		sum = buffer[index] + (byte - 48) + carry;
		carry = sum / 10;
		sum = sum % 10;

		buffer[index] = sum;
		--index;
	}

	/* if we make it here, we are at eof -- call cleanup() and return 0 */
	cleanup();
	return 0;
}



/*	Function outputSum() -- prints the sum to stdout, most significant
	character first.
*/
void outputSum() {
	int i;

	/* go past all the null characters at the beginning */
	for (i=0;i<numBytes;i++) {
		if ( buffer[i] ) {
			break;
		}
	}

	/* now write the remaining data to stdout */
	for (i=i;i<numBytes;i++) {
		putchar(buffer[i] + 48);
	}
	putchar('\n');
	return;
}

/*	Function burnSomeTime() -- wastes a random amount of time grinding
	on pointless arithmetic.  This activity makes it difficult to find
	out how much time we spend doing real work
*/
void burnSomeTime() {
	unsigned long i;

	randInt = rand() >> 5;
	for (i=0;i<randInt;i++) {
		smackMe = randInt - i;
	}
	return;
}



/*	Function setUpTimeBurner() -- sets up how likely we are
	to burn time after each string.
*/
void setUpTimeBurner() {
	howOften = (rand() % 3 ) + 1;
}






void main (int argc, char **argv) {

	buffer = (char*) malloc(numBytes);		/* allocate 8 megs of space */
	memset (buffer, zero, numBytes);		/* zero out the buffer */
	srand(time(NULL));				/* seed the random number */
	setUpTimeBurner();
	burnSomeTime();

	while (1) {
		if ( readWhiteSpace() == 0 ) break;	/* burn off the non-numeric characters */
		if ( (rand() % howOften) == 0 ) burnSomeTime();	/* burn time */
		if ( addNumber() == 0) break;		/* add the number to the sum */
	}

	outputSum();
	free (buffer);	/* just to be nice... */
	exit(0);

} /* end main */

[Editors note: - note 5 seems to be the wrong specification - perhaps the partial sums for
all orderings would be a more appropriate thing to limit?

Does this work for all numbers or just integers?

How do we get the information to and from the program without
others geting information from it?

Some other things likely to come up soon after this:
	How about paging behavior?
	How about data vs. IO time?
	...
	at which point we need a pointer to:

Lampson73: B.  W.  Lampson, A Note on the Confinement Problem, CACM
16(1), October, 1973:613-615 - This classic paper described the covert
channel problem for the first time.  The implication is that no system
that shares resources in a non-fixed fashion can ever provide perfect
separation of the sharing parties. - FC]
---------------------------------------------