Subject: Re: Executing encrypted code

From: [email-masked] (David A. Wagner)
Date: 21 Jun 1995 12:19:03 GMT

In article <[email-masked]>,
John Kelsey  <[email-masked]> 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                                             [email-masked]