Brute Force Examination of a PLD

Lets discuss the brute force examination of a PAL16R8, for example,
with absolutely no knowledge of its function.

Lets assume a 16R8.

Could we just clear all the inputs and toggle the clock line a few
times and wait for a known output (that is, if there are any of the
clocked feedback signals used, get them to the same state) and then on
the next clock state try a new input?

So...
Refresh the PAL to a known state, try value $01, try $01
Refresh the PAL to a known state, try value $01, try $02
Refresh the PAL to a known state, try value $01, try $03

Until we get a truth table with 65,535 results.

Can anyone help me think of a situation where this would NOT work?

I suppose the next "problem" would be reducing and deciphering the
equation.

Lets assume there are no GALs being tested, only a 16R8.

On 29 Dec 2005 17:13:42 -0800, "logjam" <grant@cmosxray.com> wrote:

>Lets discuss the brute force examination of a PAL16R8, for example,
>with absolutely no knowledge of its function.
>
>Lets assume a 16R8.
>
>Could we just clear all the inputs and toggle the clock line a few
>times and wait for a known output (that is, if there are any of the
>clocked feedback signals used, get them to the same state) and then on
>the next clock state try a new input?
>
>So...
>Refresh the PAL to a known state, try value $01, try $01
>Refresh the PAL to a known state, try value $01, try $02
>Refresh the PAL to a known state, try value $01, try $03
>
>Until we get a truth table with 65,535 results.
>
>Can anyone help me think of a situation where this would NOT work?
>
>I suppose the next "problem" would be reducing and deciphering the
>equation.
>
>Lets assume there are no GALs being tested, only a 16R8.

This ought to work for a 16R8, assuming you have a way to refresh to a known state (can't remember
if the register load function works after the security fuse is blown) 
The 16R8 is probably about the simplest as you don't have tri-stated outputs or combinatorial
outputs to think about. As soon as you move to a GAL the permutations rise dramatically....
   
 

Good question!  A friend and I had a discussion about a situation like that 
once.  A PAL16R8 is really quite a simple piece of logic compared to what is 
available today or even it's cousin the GAL16V8.  I say "simple" even though 
it is a 16R because is has 8 inputs and 8 outputs.  The "tricky" part of 
course is that there is a possibility that the flip-flop on each output pin 
might be directed back in to the Array, or fuse map as it is sometimes 
called.

When my friend and I discussed this "directed back in to the Array " 
possibility he had stated that it might be near impossible due to the fact 
that no one could be sure how many flip-flops were wired to go back in to 
the Array.  Could be none, could be all.  I then thought about this and 
concluded that it would be near impossible to design something useful that 
could possibly use ALL the flip-flops in the chip at once and direct the 
back in to the Array, being that there is only one Clock pin and one Output 
Enable pin, or so I believe.  *** Maybe some one can expand on this 
possibility further? ***

As far as I can tell from a design standpoint there are so many flip-flops 
to be used either as Latches or for design convenience.  I say "convenience" 
because it may be hard to wire up the flip-flop if it were on the "top" of 
the Array (say Row 0) and you needed it at the bottom (say Row 2016).  Or at 
least this is what I have come to believe and I am by no means what I would 
consider a PAL design expert.  I think these PLD's are great for something 
from the 1980's like addressing RAM, but have little if any use today, hence 
the GAL.

Now as far as trying to decipher how the PAL is programmed would be a bit of 
a mystery to me as I'm not a Math major.  I would start by using a Data 
Acquisition Unit (DAQ for short) like this one by Datx: 
http://www.datx.com/econ/prod_dt9817.htm.  Here are some neat features of 
the device.  #1 The Software.  Most important of all is the software. 
You'll need to be able to write your own code and try and formulate a 
program to send and log test signal results.  #2 Digital I/Os (DIO).  The 
unit has 28 DIOs!  Plenty for testing any PAL16.  #3 Price.  The unit is 
only $180!  Not a bad deal really.  #4 Power.  The thing I like best about 
this box is that it is USB and will supply it's own 5v power for the IC.  No 
extra power supply is needed.  Cool idea eh? ;)

Now the hard part.  Make friend with the smartest Math kid you can find and 
promise him women, lots of them if he can write a program to send an input 
to each pin of the PAL and log the results.  With time and enough results 
you should then be able to write a program to formulate a logic equation of 
what the PAL is doing.  Sounds easy, but it's not.  Then once you have some 
idea of the logic possibilities then recreate the PAL in a GAL16V8 and try 
your design in the circuit you removed the PAL from.  If it works, you'll 
need to find those women for you new buddy.  If it doesn't then I'd make a 
new Math friend. ;)

Now does any body know if there is a prewritten program that might help in 
analyzing the results from the DAQ?  I imagine there must be something.  I 
don't have enough Math background but maybe someone in this group could 
express the PAL16R8 as a mathematical equation?  I'd love to see that!

Post again and let us know how things are going.  I'd like to see the 
program you have written when your done.


Henry



"logjam" <grant@cmosxray.com> wrote in message 
news:1135905222.916789.165390@g14g2000cwa.googlegroups.com...
> Lets discuss the brute force examination of a PAL16R8, for example,
> with absolutely no knowledge of its function.
>
> Lets assume a 16R8.
>
> Could we just clear all the inputs and toggle the clock line a few
> times and wait for a known output (that is, if there are any of the
> clocked feedback signals used, get them to the same state) and then on
> the next clock state try a new input?
>
> So...
> Refresh the PAL to a known state, try value $01, try $01
> Refresh the PAL to a known state, try value $01, try $02
> Refresh the PAL to a known state, try value $01, try $03
>
> Until we get a truth table with 65,535 results.
>
> Can anyone help me think of a situation where this would NOT work?
>
> I suppose the next "problem" would be reducing and deciphering the
> equation.
>
> Lets assume there are no GALs being tested, only a 16R8.
> 

"Henry" <apl2research@comcast.net> schrieb im Newsbeitrag 
news:XKydnZQtkMWSkCjenZ2dnUVZ_sqdnZ2d@comcast.com...
> Good question!  A friend and I had a discussion about a situation like 
> that once.  A PAL16R8 is really quite a simple piece of logic compared to 
> what is available today or even it's cousin the GAL16V8.  I say "simple" 
> even though it is a 16R because is has 8 inputs and 8 outputs.  The 
> "tricky" part of course is that there is a possibility that the flip-flop 
> on each output pin might be directed back in to the Array, or fuse map as 
> it is sometimes called.
[snip]

there are ABSOLUTLY no issues reversing the R8 NO PROBLEMS

R8 has no output cells with internal tristate control meaning that all the 
FF outputs are always observable, meaning that FULL 100% guaranteed recovery 
of the fusemap is possible without any major issues

antti 

That's good news Antti, thanks!

However now I am confused why PALs slowed the counterfeiting of
computers in the early 80s.  I've read that PALs were used primarily
for component reduction but that some companies used them in ways to
slow down reverse engineering.

Was it just that a computer with I/O resources, memory, and human
knowledge of electronics slowed down the reproduction?

The HAL and PALs do not offer the ability to preload, but if all the
inputs to the PAL were low and the clock were cycled a few times and
the "brute force" program stopped on a pattern (its possible to get a
repeating pattern by clocking all 0s into the PAL) that was the same
starting pattern for all tests then that could help.

Potentially there would be two patterns, right?  All 0 inputs into the
PAL, and with the same inputs a different output.  So if the 65535
tests were begun with ONE of the initial all 0 input patterns, then
would a second set of 65535 tests on the other pin help decide the
internal feedback configuration?

This is assuming of course that the computer is processing and reducing
the test results itself.  That program/algorithm is still beyond me at
this point.  Does anyone have any ideas on a program or algorithm
written?  A book about this process?

Thanks for your time,

Grant

"logjam" <grant@cmosxray.com> writes:
> However now I am confused why PALs slowed the counterfeiting of
> computers in the early 80s.  I've read that PALs were used primarily
> for component reduction but that some companies used them in ways to
> slow down reverse engineering.

With PALs that have internal combinatorial feedback (non-registered outputs),
reverse-engineering can be significantly more challenging.

With CPLDs that have internal feedback from nodes that don't have external
visibility, it is WAY more challenging.

Back in 1981 the founders of Fortune Systems wanted a secure serial
number device to deter theft of high value software on their M68K unix
machine.  A security consultant came up with using registered Pals to
provide several uniqe sequencies that produced both a box ID andf group
ID that could independently be used to lock software to a machine, or
group of machines. Major businesses could order multiple of these
machines, then purchase a site license for the software which was group
locked. The scheme repeated ID's about every 1,000 or some PALs, which
ment that for the roughly 100,000 of the machines produced, each had
about 100 identical twins, very unlikely to ever be in the same
building/organization.

The company wanted an NDA with very heavy post employment restrictions
to be aware of the algorithms used, to protect the secrecy of the
product protection strategy, which I and a few others refused.

After I left the company, it took a couple hours with a logic analyzer
to defeat it. There wasn't a better choice in 1981 of devices. A few
years later when GAL's started being popular you could actually build
devices much harder to defeat.

logjam wrote:

> That's good news Antti, thanks!
> 
> However now I am confused why PALs slowed the counterfeiting of
> computers in the early 80s.  I've read that PALs were used primarily
> for component reduction but that some companies used them in ways to
> slow down reverse engineering.
> 
> Was it just that a computer with I/O resources, memory, and human
> knowledge of electronics slowed down the reproduction?

That, and also that something had to be copied, and so that implies
a more-legally-risky path for the copier.

> This is assuming of course that the computer is processing and reducing
> the test results itself.  That program/algorithm is still beyond me at
> this point.  Does anyone have any ideas on a program or algorithm
> written?  A book about this process?

If you have a universal programmer, they have vector testing
abilities - you can create the vectors manually, either with a text
editor, or on the PGMR itself, or with a PGM like Atmel's WinCUPL.
You can also them PGM a new copy, using a 16V8

As a first pass, you would use the programmer'd editor, to check
simple dependencies.
The same Vector file can be used to verify your RevEngineered version.

Here is an example of a 20 Pin PLD JED file, Test vector section :

Input values are 0,1,X and output values are H,L,Z
X tests both 0 & 1, but a string of XXXXX does not
usually do 32 tests.


*P 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
*V0001 011110000NXHLHHL1H1N
*V0002 011110000NXHLHHL0H1N
*V0003 011110000NXHLHHL1H1N
*V0004 001110000NXLHHHL1H1N
*V0005 011010000NXLHHHL1H1N
*V0006 010110000NXLHHHL1H1N
*V0007 011100000NXLHHHL1H1N
*V0008 011110000N0HLHHL0H0N
*V0009 111110000N0HHLHH0H0N
*V0010 011110000N0HLHHL0H0N
*V0011 101110000N0HHLHH0H0N
*V0012 011110000N0HLHHL0H0N
*V0013 111010000N0HHLHH0H0N
*V0014 011110000N0HLHHL0H0N
*V0015 110110000N0HHLHH0H0N