From dawagner@flagstaff.princeton.edu Wed Jun 21 08:45:59 EDT 1995
Article: 36298 of sci.crypt
Path: cnn.Princeton.EDU!flagstaff.princeton.edu!dawagner
From: dawagner@flagstaff.princeton.edu (David A. Wagner)
Newsgroups: sci.crypt
Subject: Re: Executing encrypted code
Date: 21 Jun 1995 12:19:03 GMT
Organization: Princeton University
Lines: 45
Message-ID: <3s92nn$nil@cnn.Princeton.EDU>
References: <Bi18244.jmkelsey@delphi.com>
NNTP-Posting-Host: flagstaff.princeton.edu

In article <Bi18244.jmkelsey@delphi.com>,
John Kelsey  <jmkelsey@delphi.com> wrote:
> 
>      As an alternative, how about
> 
>      write v to address A:
>           Memory[A] = (t+A) xor E(K,(t+A) xor v)
> 
>      read v from address A:
>           v = (t+A) xor D(K,(t+A) xor Memory[A]) ?
> 
>      The t parameter can be used to allow for relocation of blocks
> of data in the address space.  I think t should be kept secret.
> 

No go.  Here's how to derive t if it's kept secret.

Write v to address A, and write v' = v xor 1 to address A+1:

Memory[A]   = (t+A)   xor E(K, (t+A) xor v)
Memory[A+1] = (t+A+1) xor E(K, (t+A+1) xor v xor 1)

Now note that the lsb of t+A is 0 iff

	(t+A) xor v  =  (t+A+1) xor v xor 1;

but this condition holds iff [actually, it's not iff, but
it's probabilistically damn close]

	Memory[A] xor Memory[A+1]  =  1

which is easily detected by peeking at the RAM.

So that trick finds the lsb of t.  You can continue via the
same method to find the rest of the bits of t.

Thus, keeping t secret can't give you any extra security.

But when t is publicly known, your method falls apart, and
is no better than the naive

	Memory[A] = E(K,v).

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu