| Author |
Message |
Guest
|
 Posted:
Fri Feb 11, 2005 12:22 am Post subject:
Instruction Reduction |
|
|
Hello,
Tanenbaum says in his Structured Computer Organization book that all
instructions can be reduced to:
1. An addition operation
2. Check to see if a number is zero
3. Copy data from one memory location to another
I was wondering if anyone can point me to a chart for instance, that
shows such a reduction (I'm guessing mostly with regard to number one
above). To further clarify, I guess, I can derive for instance, an xor
operation with only using additions, etc. Of course, a program with
such a primitive instruction set would be large (similar to coding in
binary I guess).
I'm actually doing research in program obfuscation/protection. Anyway,
I'm a high-level programmer who occasionally ventures to the low-level
in such cases.
Thanks,
--Willard |
|
| Back to top |
|
 |
Guest
|
| Posted:
Fri Feb 11, 2005 8:02 am Post subject:
Re: Instruction Reduction |
|
|
wthompso@cs.fsu.edu wrote:
| Quote: | I was wondering if anyone can point me to a chart for instance, that
shows such a reduction (I'm guessing mostly with regard to number one
above). To further clarify, I guess, I can derive for instance, an
xor
operation with only using additions, etc. Of course, a program with
such a primitive instruction set would be large (similar to coding in
binary I guess).
|
You didn't say if you were targeting source or object code protection.
You might need to view those operations at the bit rather than byte
level. (I never saw that quote of his so I don't know exactly what he
means.) If so, you'd be able to model state driven logic with them
much like how something would be written in VHDL. Unfortunately that
means you have to rewrite the algorithm as synthesizable logic.
However, once you have synthesized "gates" out of the algorithm, all
sorts of nasty transforms are possible because gate ordering is
irrelevant provided you iterate over them enough times to ensure
propagation from logic cone inputs to logic cone outputs. (Sort of
like transitive closure.)
If you really want to obscure an algorithm, it might be far easier to
write or modify an existing virtual machine/emulator (e.g., look in the
src/cpu directory for the MAME project) as then hackers have two
programs to figure out, not just one. IIRC, the "type in word xxx on
line yyy page zzz" protection in some Sierra games was giving crack
groups fits for a while back in the early 90s as they had to deal with
encrypted, interpreted code. A quick example of how you can mess with
code for a virtual machine (assume a powerpc):
1) The instruction fetcher part of the code XORs the effective address
of an ifetch with 0x8 in some regions to get the "fixed" EA. They're
stored in memory accordingly swapped.
2) Some opcodes are remapped (e.g., "and" and "or" are swapped)
3) Register fields are re-ordered (e.g., rA and rB)
<etc> Then if a hacker gets so far as to realize you're using PPC, he
thinks he's looking at legitimate code and attempts to analyze it. The
key is not to overdo it, but to break enough of the function that it's
useless, however looking at the algorithm casually seems to make sense
as branch targets are fine, etc. (Especially with creative use of #2
and #3.) In that way they waste time analyzing useless code instead of
digging into your virtual machine's nonstandard instruction scheme.
Some arcade hardware does this type of encryption on its ROMs.
-Tony |
|
| Back to top |
|
|
Guest
|
| Posted:
Sat Feb 12, 2005 7:37 am Post subject:
Re: Instruction Reduction |
|
|
| Quote: | You didn't say if you were targeting source or object code
protection. |
Both. More specficially my research consists of protecting the
integrity of mobile code. In order to do that the program's (semantic)
privacy must be protected *somehow*. I assume that the program can be
reverse engineered, thus, black-box of the original program and the
"encrypted" program must not be the same. This is easily done
exclusively at black-box by simply appending a random number generator.
The question then becomes how do we do this in white-box.
This problem (i.e. the malicious host problem) is difficult to solve,
thus I don't mind discussing my direction since I've spent quite some
time on it now as well as others. High-level program constructs are
difficult to scramble (in the black-box sense mentioned above). Thus,
I was wondering whether or not more primitive instruction sets could be
easier to encrypt. I'm finding that there really is no difference.
Because the program has to execute in the remote hosts space regardless
of its instructions.
Furthermore, I'm also struggling with our (frail) laws of C.S., i.e.
whether or not what I'm attempting to do is (generally/systematically)
possible via Rice's theorem and self-halting reduction, etc. The (very
small) programs that I encrypt have an enormous code explosion (not
provably secure size, though), so much so that they, more than likely,
would not be practical.
| Quote: | You might need to view those operations at the bit rather than byte
level. (I never saw that quote of his so I don't know exactly what
he
means.) If so, you'd be able to model state driven logic with them
much like how something would be written in VHDL. Unfortunately that
means you have to rewrite the algorithm as synthesizable logic.
However, once you have synthesized "gates" out of the algorithm, all
sorts of nasty transforms are possible because gate ordering is
irrelevant provided you iterate over them enough times to ensure
propagation from logic cone inputs to logic cone outputs. (Sort of
like transitive closure.)
|
This sounds like a lot of overhead.
| Quote: | If you really want to obscure an algorithm, it might be far easier to
write or modify an existing virtual machine/emulator (e.g., look in
the
src/cpu directory for the MAME project) as then hackers have two
programs to figure out, not just one. IIRC, the "type in word xxx on
line yyy page zzz" protection in some Sierra games was giving crack
groups fits for a while back in the early 90s as they had to deal
with
encrypted, interpreted code. A quick example of how you can mess
with
code for a virtual machine (assume a powerpc):
1) The instruction fetcher part of the code XORs the effective
address
of an ifetch with 0x8 in some regions to get the "fixed" EA. They're
stored in memory accordingly swapped.
2) Some opcodes are remapped (e.g., "and" and "or" are swapped)
3) Register fields are re-ordered (e.g., rA and rB)
etc> Then if a hacker gets so far as to realize you're using PPC,
he
thinks he's looking at legitimate code and attempts to analyze it.
The
key is not to overdo it, but to break enough of the function that
it's
useless, however looking at the algorithm casually seems to make
sense
as branch targets are fine, etc. (Especially with creative use of #2
and #3.) In that way they waste time analyzing useless code instead
of
digging into your virtual machine's nonstandard instruction scheme.
Some arcade hardware does this type of encryption on its ROMs.
|
I appreciate your response regarding the virtual machine and I will
again look into it, wrt what you're saying. If I can just say that the
virtual machine idea from what I know, would not be too secure unless
maybe it is unique each time. In other words, the ins and outs of the
VM would eventually be disclosed to an adversary, thus, he would know
how to reverse engineer it, etc. The adversary can easily look at the
underlying operations of the VM since it is all in his space. In your
descriptions however, there may be a way to obtain some kind of
uniqueness, that is, perhaps using some kind of parameterized key in
how the VM would arrange opcodes and registers, etc.
Ultimately, we assume that for mobile code the remote host can do
anything he wants with the code. The aim is to be able to reduce
*effective* tampering to *blind* tampering thus giving mobile code such
as mobile agents, greater survivability within an untrusted network.
Lastly, I'm going to digest some of the things you've mentioned in more
detail. If there is anything else you can add or make adjustments to
based what I mentioned above, that would be great.
Thanks,
--Willard |
|
| Back to top |
|
|
Scott A Crosby
Guest
|
| Posted:
Sat Feb 12, 2005 12:50 pm Post subject:
Re: Instruction Reduction |
|
|
On 10 Feb 2005 11:22:16 -0800, wthompso@cs.fsu.edu writes:
| Quote: | Hello,
Tanenbaum says in his Structured Computer Organization book that all
instructions can be reduced to:
1. An addition operation
2. Check to see if a number is zero
3. Copy data from one memory location to another
I was wondering if anyone can point me to a chart for instance, that
shows such a reduction (I'm guessing mostly with regard to number one
above). To further clarify, I guess, I can derive for instance, an xor
operation with only using additions, etc. Of course, a program with
such a primitive instruction set would be large (similar to coding in
binary I guess).
|
This may be of interest:
@article{121976,
author = {P. A. Laplante},
title = {A novel single instruction computer architecture},
journal = {SIGARCH Comput. Archit. News},
volume = {18},
number = {4},
year = {1990},
issn = {0163-5964},
pages = {22--26},
doi = {http://doi.acm.org/10.1145/121973.121976},
publisher = {ACM Press},
}
| Quote: | I'm actually doing research in program obfuscation/protection. Anyway,
I'm a high-level programmer who occasionally ventures to the low-level
in such cases.
|
This may also be of interest:
@article{barak01impossibility,
author = "Boaz Barak and Oded Goldreich and Rusell Impagliazzo and Steven Rudich and Amit Sahai and Salil Vadhan and Ke Yang",
title = "On the (Im)possibility of Obfuscating Programs",
year = "2001",
}
Scott |
|
| Back to top |
|
|
Anthony J Bybell
Guest
|
| Posted:
Sun Feb 13, 2005 7:56 am Post subject:
Re: Instruction Reduction |
|
|
wthompso@cs.fsu.edu wrote in message news:<1108175839.973517.35720@z14g2000cwz.googlegroups.com>...
| Quote: | Ultimately, we assume that for mobile code the remote host can do
anything he wants with the code. The aim is to be able to reduce
*effective* tampering to *blind* tampering thus giving mobile code such
as mobile agents, greater survivability within an untrusted network.
|
Read the pdf on the top of the page listed in the URL. There are some
interesting observations there which save me a lot of typing as he's
thinking along the same track I am:
http://www.xenatera.com/bunnie/proj/anatak/xboxmod.html
....code signing (authentication) from a secure boot ROM all the way
out is probably the only "really" secure method out there as the
security is based on mathematical probability rather than obscurity.
Otherwise, given enough time, if your device is interesting enough its
hack will make the front page of Slashdot: there are a lot of clever
people with a lot of free time on their hands out there.
This goes without saying, but make sure that JTAG/I2C/etc is disabled
on your remote host. =)
-t |
|
| Back to top |
|
|
George Neuner
Guest
|
| Posted:
Mon Feb 14, 2005 5:30 am Post subject:
Re: Instruction Reduction |
|
|
On 10 Feb 2005 11:22:16 -0800, wthompso@cs.fsu.edu wrote:
| Quote: | Hello,
Tanenbaum says in his Structured Computer Organization book that all
instructions can be reduced to:
1. An addition operation
2. Check to see if a number is zero
3. Copy data from one memory location to another
I was wondering if anyone can point me to a chart for instance, that
shows such a reduction (I'm guessing mostly with regard to number one
above). To further clarify, I guess, I can derive for instance, an xor
operation with only using additions, etc. Of course, a program with
such a primitive instruction set would be large (similar to coding in
binary I guess).
|
Tanenbaum is probably correct ... I haven't given it enough thought.
If you're interested in reading about a real computer with a sand
simple instruction set, Lincoln Lab's TX-0 (tee-ex-zero) "tixo"
computer had only 4 instructions: store, add, conditional branch, and
a "trap" instruction that accessed system registers, performed I/O and
a few other useful things based on the operand. There's some stuff
about it online at:
http://www.bitsavers.org/pdf/mit/tx-0/
and
http://www.tixo.org/
I don't know of any ready references for the kind of code reduction
and/or simplification you're interested in. Your best bet might be
to find and look at some actual tixo code to see how real problems
were attacked with the limited instruction set.
There's not much "interesting" code at the above links, however,
there are some MIT lab memos at bitsavers.org which talk about
applications and code libraries being made available for the tixo. If
you are able to locate the actual code for some of the more
interesting ones (assembler, debugger, FP interpreter) I'm sure you
could learn a lot by studying it.
George
--
for email reply remove "/" from address |
|
| Back to top |
|
|
del cecchi
Guest
|
| Posted:
Mon Feb 14, 2005 5:56 am Post subject:
Re: Instruction Reduction |
|
|
"George Neuner" <gneuner2/@comcast.net> wrote in message
news:a8ov01pue9fn68k7o4bt8a01hoef25ffmg@4ax.com...
| Quote: | On 10 Feb 2005 11:22:16 -0800, wthompso@cs.fsu.edu wrote:
Hello,
Tanenbaum says in his Structured Computer Organization book that all
instructions can be reduced to:
1. An addition operation
2. Check to see if a number is zero
3. Copy data from one memory location to another
I was wondering if anyone can point me to a chart for instance, that
shows such a reduction (I'm guessing mostly with regard to number one
above). To further clarify, I guess, I can derive for instance, an
xor
operation with only using additions, etc. Of course, a program with
such a primitive instruction set would be large (similar to coding in
binary I guess).
Tanenbaum is probably correct ... I haven't given it enough thought.
If you're interested in reading about a real computer with a sand
simple instruction set, Lincoln Lab's TX-0 (tee-ex-zero) "tixo"
computer had only 4 instructions: store, add, conditional branch, and
a "trap" instruction that accessed system registers, performed I/O and
a few other useful things based on the operand. There's some stuff
about it online at:
http://www.bitsavers.org/pdf/mit/tx-0/
and
http://www.tixo.org/
I don't know of any ready references for the kind of code reduction
and/or simplification you're interested in. Your best bet might be
to find and look at some actual tixo code to see how real problems
were attacked with the limited instruction set.
There's not much "interesting" code at the above links, however,
there are some MIT lab memos at bitsavers.org which talk about
applications and code libraries being made available for the tixo. If
you are able to locate the actual code for some of the more
interesting ones (assembler, debugger, FP interpreter) I'm sure you
could learn a lot by studying it.
George
--
for email reply remove "/" from address
|
Or you can google comp.arch archives. Look for "single instruction
computer" or "minimal instruction set" and stuff like that. Couple
years back, as I recall. I didn't pay much attention.
del cecchi |
|
| Back to top |
|
|
Guest
|
| Posted:
Mon Feb 14, 2005 6:56 am Post subject:
Re: Instruction Reduction |
|
|
Hi Scott,
Scott A Crosby wrote:
| Quote: | @article{121976,
author = {P. A. Laplante},
title = {A novel single instruction computer architecture},
journal = {SIGARCH Comput. Archit. News},
volume = {18},
number = {4},
year = {1990},
issn = {0163-5964},
pages = {22--26},
doi = {http://doi.acm.org/10.1145/121973.121976},
publisher = {ACM Press},
}
|
I'll definitely look into this. I received an email from someone
regarding a single instruction computer but I haven't yet checked that
out.
| Quote: | @article{barak01impossibility,
author = "Boaz Barak and Oded Goldreich and Rusell Impagliazzo
and Steven Rudich and Amit Sahai and Salil Vadhan and Ke Yang",
title = "On the (Im)possibility of Obfuscating Programs",
year = "2001",
|
I've already read this paper and definitely see what these guys are
advocating. However, we are not doing obfuscation exactly. It's a
keyed-based semantic tranformation, but if the code seems obfuscated as
a result then that's fine.
Thanks for your help.
--Willard |
|
| Back to top |
|
|
Guest
|
| Posted:
Mon Feb 14, 2005 7:00 am Post subject:
Re: Instruction Reduction |
|
|
Thanks everyone for your help. I will certainly look into all of these
as soon as possible.
Sincerely,
Willard |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in