Brute forcing 68k era PALs & GALs

[Trash80toHP_Mini]

I figure LINUX is the place for this kind of work. It's light years beyond my techs and maths. Might have been tried, but gotta ask:

There aren't all that many inputs and outputs on programmable logic of the era, so we're talking about a large, but finite set of operations?

IF a "reader" is built to generate and record all WHEN this THEN THATS in a GAL's operations?

Might there be a way to reduce that set to a table of general operating procedures?

Might there also be a way to deduce a set of possible formulas from those generalized procedures.

My gut tells me we might be in the realm of digital signal processing transforms, which I've read a bit about and why I'm asking. Totally out of my depth here. :-/

 

[trag]

If all the logic inside of PLDs was "combinational" then your supposition would be true.   That is, if for every input set X, one got an output set Y, which never varied, then decoding small PLDs would be trivial.*

However, PLDs have internal flip/flops which is a tiny amount of logical memory.   So the problem can change from, "What output do you give me for this unique input?" to "What output do you give me for this unique input when the previous input was X?"     Add in the possibility of putting registers multiple levels deep and the problem can reach tremendous complexity.

Fortunately, in most cases, the PLD will be programmed as simple combinational logic as there just aren't that many instances where the previous clock cycle's state influences how the next one should behave.     Although, I could see it coming up quite often when controlling/adapting DRAM.     Sometimes a CAS signal indicates the final step in a read or write operation, but depending on the previous stare of RAS, it might be the first step in a refresh operation.

*  I mean trivial in the mathematical sense.   It can still be a pain.   The job almost requires that one draft out a schematic of the PLD in the circuit and figure out which pins are being used as inputs and which are being used as outputs.

 

[Trash80toHP_Mini]

The job almost requires that one draft out a schematic of the PLD in the circuit and figure out which pins are being used as inputs and which are being used as outputs.

Yeah, good point, I was thinking that you'd set those parameters from the hardware target up in the reader's inputs to cut huge swaths out of the set to be sampled. There's also the case of one GAL present on the SE version of the Performer Accelerator that's not present on the Killy Klipped version. Some of the inputs and outputs are tied together within the GAL's footprint for clocking shenanigans.

My interest was piqued by pattern recognition in human vision long ago and wondered where that kind of thing had gotten in terms of the maths involved. We've got a whole lotta cycles to burn these days as compared to what was available in the early nineties. The hardware aspects of the sampling are now so much more advanced than then at the hobbuist's level in this age of Pi. It made me think of this and if anyone had had a crack at it before? I remember reading some things about brute forcing, but wondered  .  .  .

 

[Trash80toHP_Mini]

If all the logic inside of PLDs was "combinational" then your supposition would be true.   That is, if for every input set X, one got an output set Y, which never varied, then decoding small PLDs would be trivial.*

Ayup, that case would pretty much make it a fancy ROM, no? My thinking was more along the notion of using the sample to differentiate between "combinational" and "operational." Then apply maths to search patterns within that latter subset. Not so good at putting this kind of thing into words. :-/

 

[trag]

Similar to a ROM, and you can actually use a ROM as a PLD if you have a complete truth table.  But the internal operations are different.

 

[Gorgonops]

So, basically, the difference is that with a PLD it's possible to build a state machine that's entirely internal to the chip. Strictly speaking that doesn't necessarily make it it *impossible* to reverse engineer it by simply rattling through all the possible inputs and monitoring the outputs it does, as noted, make it far more difficult since the internal state machine may completely change the output response to a given set of inputs when a certain combination of inputs triggers it to do so. And since the trigger can be timing or sequence dependent then, well, even at "computer speeds" it may well take a *long, long time* to test every possible state. I imagine even a fairly small PLD could easily be programmed in such a way that it would take essentially infinite time (IE, heat death of the universe sort of scale) to try to reverse engineer it with a simple monkeys-on-typewriter approach.

 

[Trash80toHP_Mini]

Shakespearean monkeyworks might be well be a red shift reversal level problem, but we're not even remotely talking about that kind of data set. I think it's a given that it's possible to reduce the sample set to operations possible and even to those probable based on an understanding of architecture/design application of simple GAL logic on the one side. A complex state machine can be built in the the well documented logic in the array, but in the applications in which I've seen them used in 68k systems doesn't appear to require all that much complexity on the other.

A blown security fuse at the time was enough security to protect a company's work from any serious attacks available at the time. None of it was earth shatteringly important or even in need of more than that simple safeguard, it just wasn't something to be freely distributed. So it should be an entirely different story than your typewriter thing.

Different time, different tools, interesting problem, to me anyway.

 

[joethezombie]

Since early PLDs have a significant product term limitation, and only support 4 types of latches and flip-flops, it should be somewhat reasonably possible to limit the guesses to a specific set of test procedures.  I've been toying with such since PowerCache using an Arduino Mega, but have yet to realize any functional code.  It helps that early PALs have some outputs that must stay outputs, and and only a few outputs that are configurable as tri-state or feedback.   It's when we get into GALxVx territory that counters and other registered features can blow the possibilities out of the universe.  Internal functions which act as output enables are pretty damn good at covering their tracks.  But as far as vintage Mac hardware, such uses are probably very limited.

 

[Gorgonops]

I think it's a given that it's possible to reduce the sample set to operations possible and even to those probable...

The "Monkeys on Typewriters" example I threw out there is, of course, a ridiculous worst-case scenario. (IE, someone chucks a PAL or GAL in your lap with you having no idea where it came from and you being expected to accurately replicate it based only on black-box probing.) Obviously if you have the thing it came from in-hand, you know broadly what it's supposed to do, and you have data sheets for the chips it's tying together then, sure, you *might* be able to come up with an algorithm to fill in the gray areas. Still, giving a "sure, you could do this" or "no, that sounds awfully hard" answer depends a lot on scoping your question with more specificity. Replicating, say, the PALs in a Mac Plus that only replace a very small handful of discrete TTL parts and who's internal architecture can be strongly guessed at based on extrapolation is a totally different kettle of fish from churning out a copy of some big square mysterious GAL on a video card.

 

[Trash80toHP_Mini]

The "Monkeys on Typewriters" example I threw out there is, of course, a ridiculous worst-case scenario.

Got that, liked that. Switch it up to one very fast little monkey playing Tetris and it's a pretty good analogy, but I'll try to do better:

A robotic arm assembling a limited set of Lego blocks to derive or create a new 3D model of a path through an unknown Escher building from the footings of the foundation as the entrance would be better. Specifications for the structure would be defined by requirements for the gabled windows at the exit. Recreating THE scaffold design present in the GAL isn't necessarily the point. Iteratively refining A scaffold design from footings to windows would be more the goal of the exercise. Foundation block placement and gable framing possibilities presented to the architect in something akin to a computer generated scatterplot would be what I'm trying to describe.

3D Chess would be an oversimplified model. Arrangement of the pieces of both sides at start of game are known. Checkmate has been achieved in one game. Achieving Checkmate via any game play is the requirement. The computer player's task would be to present the paths to Mate from both sides of the game to the judge, where human visualization and intuition would iteratively refine play from that presentation until Checkmate can be achieved by any of many strategies.

I've been toying with such since PowerCache using an Arduino Mega, but have yet to realize any functional code.

That's actually what got me on this kick, joe. Using statistics/probabilities for you to realize functional code imagery from sets of mathematically generated snapshots is what I see..

To put it a different way, You've got set air forces available to achieve destruction of strategic targets. You plan and execute the first mission from requirements defined by strategy, Computation would be reconnaissance assets. You would then be presented with quantities of flat photos for examination in offset pairs stereoscopically. You note positive results, refine targeting data, plan and execute the next attack mission and so on.

The start and end points are known, it's A journey that's the exercise, not recreation of THE path to the end of the journey.

Coffee is kicking in so I'm losing it, hope this drivel makes some kind of sense to somebody. :blink:

 

[Trash80toHP_Mini]

OK, just made the transition from artist to craftsman in the shower and came up with a new one.. Computer chess has been a thing since the beginning. Could documented algorithms developed for the game be adapted to this problem? Now I see it as a known arrangement of pieces on each side of the board. Combinatorial processes take place on that plane and Operational processes would be multiple plane moves above and below the board achieved by formulaic function.

 

[techknight]

If your PAL is an L series its easy to reverse using an analyzer built on the Arduino or other. if its an R series, well.... 

Dont feel bad, I am trying to reverse the bitstream of an XC2015 FPGA. 

 

[Trash80toHP_Mini]

I don't really know jack about this stuff, but I did ace a symbolic logic final in something like fifteen steps that I don't think even the professor saw coming. I SEE logical functions and how they fit together, interlocking like a bar puzzle, though I have trouble explaining anything in words, that's not the way I think. :-/

What I've been trying to get across is that examining the possibilities for the first few steps deep on the input side side and backtracking possibilities a few steps back from the output side based upon knowing the architecture of the system from both ends might yield a very large, but finite set of logical functions which might have been employed. This could lead to better guesstimates as to possible formulas developed, further reducing the set of logical functions applicable and the process repeated with each refinement.

Not talking about trying to READ the exact fusemap burned into a logical array, but about attacking it more in the manner of codebreaking by searching for patterns in the data produced by such an Arduino based analyzer. Something like frequency analysis of the the input/output table would be the most simple example I can think of offhand. If you can guess at what logical functions might be possible equivalents to letter of the alphabet possibilities identified by frequency analysis you might "see" patterns not identifiable by examination of the raw data.

Dunno, thinking about this kind of stuff works better in morning caffeine deprivation mode.  :blink: