Another useful attack vector - the RET instruction.
Assuming the tool Chip used sets src and dst to zero, all RET should have the same scrambled values except for any conditional execution part. Ignoring IF_NEVER, all RET instructions have between 6 and 9 bits set, the rest cleared, 9 bits set for an IF_ALWAYS RET.
Applying a bit-count puts a valid 'IF_ALWAYS RET' at 1E4, just before the constant which looks like -1 ... coincidence ? Or that -1 would be the first constant chosen to appear after code ?
On the counter-side, there are not as many scrambled longs which have the same value which suggests a lack of IF_ALWAYS RET, which seems unlikely.
Another target is IF_ALWAYS JMP #? which should have between 10 and 17 bits set. Any other instructions which should have a narrow band of bits set ?
Another interesting thing is that there are no zeroed longs in the Cog as one would expect for uninitialised variables ( zeroed longs exist in the loader part ). I suspect this is because run-time variables are overlaid on Cog Code once that has been executed and becomes redundant. The most obvious, executed and re-usable are at $000 up, so that may prove useful with src and dst registers mainly being zero bits elsewhere.
One final thought for now - Most of us are, in general, attacking the interpreter code; would a better approach be to attack the 'simpler' bootloader or even start with the constants loaded to the Cog ?
Yes I'm pretty sure the bit swapping permutations are given by 32! which is 2.6e+35. That's far more secure than a 32 bit constant XORed into all the words.
Checking one per second, that would take 8.3e+27 years to do brute force. Even getting the check down to milliseconds pre permutation won't practically help much.
It reminds me of the eternity puzzle. www.google.co.uk/search?q=eternity+puzzle&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US[noparse]:o[/noparse]fficial&client=firefox-a A jigsaw variant that offered £1,000,000 to the first person to solve it. The permutations were so huge that no foreseeable supercomputer could brute force the solution given millions of years. Yet the problem was understood and a way of whittling down the permutations was found which resulted in a solution being found by brute force in just a few months.
The key to that was one of parity. As I recall the pieces were conceptually made of several right angled triangles. Some left handed triangles, some right handed. So a given piece might have more right handed triangles in it, or more left handed pieces, or the same number. This gave a "parity" for each piece. It so happened that when a program was doing a search of permutations,, you could check the parity of the pieces you have left against the parity of the space left on the board to fill, and rule out a whole branch of the search tree.
Your suggestion of counting the number of ones and zeros in a long is parity too. If this is a bit swap situation, that does seem like a very promising angle to pursue.
I take that back. There was much talk of using parity to help solve eternity, but I've just read up the method that the winners used, and they didn't use parity, and suggest parity is useless for that puzzle. But that doesn't mean it won't be useful here.
I have had a fun morning reading this thread. I REALLY enjoy this forum but I am not enough of a propeller head to help with the search. I think it is interesting that Chip says there might be a solution to code protection in PropII and then sends us on this quest. I have to assume the new PropII feature is making this "utility" available to us. If that is true and we are able to break it then the "utility" would be useless in the future PropII.
That said, I don't think this "utility" can be based on static scrambling code; if it was then once you knew the trick all would be revealed. There has to be a key to make this work for the future and that key must be truly hidden in the scrambled image. I would think that with the "trick" understood you could find the key if you had both the source and scrambled images. Obviously you can extract the source if you have the scrambled and the key but cracking the scrambled without the key must be a serious effort even when you know the trick.
To make this a practical solution for the PropII you would need to prove that you coudn't find the key in someone's object based on numerous experiments where you have both the source and scrambled versions of your own code.
Have fun and I will continue to watch. I think the PropII will be well worth the wait.
There are the right number of bits in the first long and in the second for each of those instructions, plus the right number of changes ( bit sets and bit clears ) between the two. It's also what one would expect as there are five words which are in the info block the interpreter needs to use. Following should be some sort of copy/load from Hub code.
If correct, then it narrows down the potential bit swapping possibilities; one of three bits cleared maps to the I (immediate) bit, the other two to bits 0 and 2 (src), the six bits set map to bits 4 through 9 ( src, and lsb of dst ). The set and unchanged bits map to bit 29 and 31 (opc) and the other five to R and the four Condition bits.
Applying that to the constant at 1E8 would be interesting.
As I've pointed out before, given the number of times certain longs are repeated, there's almost no chance that any kind of cumulative enciphering is afoot. This means that the same transformation is being applied to each long.
I've done some analysis on consecutive groups of 6 bits, using all possible rotations of the long and all possible 6-bit XOR patterns, in both forward and reverse order. What I was looking for was a reasonable instruction distribution (i.e. no MUL, MULS, ENC, or ONES; few, if any, WAITxx; lots of JMPRETs (same as JMPs)). So far, nothing stands out. Here's a sample of the program's output:
This, of course, is not a real candidate, since there are no hub instructions. Obviously, I need to hone my filter somewhat.
It's still possible that the target of a MOVI, for example, could be encoded as a MUL, say, to throw people off the scent. I would have to look at the bytecode list to determine if there's any correspondence between their bit patterns and those of the actual ASM instructions they represent. If so, a MOVI in the interpreter would make perfect sense. In any event, I suspect, as you do, that some bit-swapping/nybble-swapping/byte-swapping is taking place. It would be easiest to analyze if the swapping were local, but that 00000008 suggests otherwise and is what originally put me on the trail of rotations. The FFFFFFFF that precedes it suggests that there is no XORing taking place at all. So my next thrust will be looking at likely bit permutations.
Yes, my endianess is probably wrong ( I just pulled the data as is out of the SPIN.HEX file posted elsewhere ), but shouldn't matter if bit-swapping is the key, but it would help if we all use the same raw data and agree which bit is which.
On your dump, don't forget that $F000-$F002 are part of the trig tables, and the Interpreter starts at $F004. I don't see any reason why the Cog wouldn't load 496 longs from $FFF4 onwards, thus no lsb-to-lsb mapping of ROM to Cog address ( for loader at $F800 there would be ). What's at 'unused' $F002..$F003; no idea ( is that the $02CA or $FFFF - unprogrammed ? )
I'm doing my decoding by hand based on counts of bits-set and guessing what the instruction could be. That at $003 could be a "MOV $003,#0", although there are other dst/src possibilities. If so it looks like bit 25 ( my endian ), bit 8 ( your endian ) is the I, immediate, bit. After that it gets more complicated; RDWORD, JMP, CALL ?
I've been working on how many bits are set or cleared compared with the suspected "MOV $000,#5" and which possible instruction those changes could give. That's still a lot of possibilities for each instruction, meaning scouring for changed-by-N bits instructions doesn't seem worthwhile yet. It is however possible to say what instructions something cannot be through too few bit changes. If the I bit mapping has been identified, that allows encrypted values of "MOV $000,#$000" and "MOV $000,$000" to be determined, a reasonable basis to base further bit-changes from.
Looking at where the bit changes are if it is as I've guessed for $000 and $001, it's 'random' bit swapping although some pattern could emerge. Handily consecutive bits, byte or nibble, unfortunately I don't think so.
Unfortunately, I haven't come up with a strategy for attempted decoding which can be automated yet.
I looked at Spin bytecode function to PASM opcode mappings which would make them easer to decode and handle using MOVI within the interpreter and I didn't see any obvious one-to-one mappings.
I don't use the value at F000. It's just there to keep the columns lined up. The FFFF is part of the sine table. 'No idea what the 02CA is for. One thing I forgot to mention is that when I do my analysis, I ignore that part of the code which comes near the end, since it's probably data and not instructions.
A peculiar thought occurred to me: Suppose part of the trig table, when interpreted as code, was actually able to write something to hub memory. One could then start a cog beginning in the trig table that would include part of the interpreter code. It would be a huge coincidence, but if just one or two longs from the interpreter code got written out to hub memory as a result, that could provide a huge clue as to how the bits are scrambled.Update: Never mind. There's nothing in the 512 longs preceding F004 that starts with 0 in the upper nybble.
Also, even though there are 32! bit permutations, one wouldn't have to examine nearly that many. For the i-field, there are "only" 32! / 26! possibilities -- still a large number, but accessible for exhaustive analysis on a fast computer. By partitioning opcodes into groups for frequency analysis, that number could be reduced even further. Once the opcode bits have been determined, any pattern extant in their selection might provide a clue for the other 26 bits.
-Phil
Post Edited (Phil Pilgrim (PhiPi)) : 2/21/2008 9:24:38 PM GMT
If there is no XOR and only permutations in the scrambling, then checksums can find candidates for certain instructions.
Then guessing a couple of instructions correctly ... quickly decreases the number of possible permutations,
and rapid successive approximation may happen as testing remaining permutations reveals more good instructions.
Another totally different idea:
Maybe the spin interpreter is a double interpreter,
so it squeezes more instructions in 496 longs.
Also, does the bootloader need all the memory reserved for it?
(Doesn't it have to be Spin bytecode to be able to run at all outside a cog? Maybe I missed something.)
I assume, since you asked, that perhaps one of us has determined something. As much as I'd prefer not to know just yet what it might be, I'll happily defer to the majority, although it may have to wait until morning for Hippy in the UK. (I know you're just dying to tell us!)
The Propeller instructions divide nicely into 16 groups of four related opcodes which differ among themselves in their two LSBs. Therefore it's possible to perform a reasonable opcode frequency analysis on these 16 groups, rather than on all 64 opcodes. This reduces the permutation search space from 605,854,080 to 863,040 instances.
I've run some analyses over the latter space, hoping to find candidate permutations bearing some sort of pattern. My criteria were the following, relating to the number of instructions found:
····MUL group = 0 ····WAIT group < 5 ····MOVS group (includes JMPRET, JMP, RET) > 20 ····MOV group > 20 ····RDBYTE group > 20 ····Any single group < 128
I found plenty of candidates, but no permutations bearing an obvious or simple pattern. Assuming that permutation is the sole obfuscation method used, this could be due to a couple factors:
1. Chip's chosen permutation employs a non-regular pattern.
2. There is data interspersed among the instructions that code into the MUL group, thereby disqualifying the permutation that produced them.
I assume, since you asked, that perhaps one of us has determined something. As much as I'd prefer not to know just yet what it might be, I'll happily defer to the majority, although it may have to wait until morning for Hippy in the UK. (I know you're just dying to tell us!)
-Phil
Well, I don't want you guys to suffer burnout. I'd hate to see you run too far down the wrong road and get all fatigued and give up. Then, I'd never have the pleasure of showing you my code. Aaaaaaah.... I guess we can all wait.
Should I quit with the psyops? Is it helping or hurting?
Does the interpreter use up every long in a cog, or is there room for a loop to copy its (decrypted) self into hub memory for dumping. I believe I would need four longs to do it.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I am 1010, so be surprised!
I was just playing with changing the listing to big endian and disassembling it, starts with
IF_C_EQ_Z RDLONG $14C #$001 WC, reads the global clock speed
IF_Z HUBOP $0B8 #$01A WC NR , equates to a nop without Z set
then a rdlong of long 1 which includes the global clock register,
this is sounding like a good start for an interpreter that needs to know how fast it is going
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.
The wrong turns are part of the fun. But please feel free to taunt us all you want!
I'm curious, though: why the sudden decision to release the interpreter code? I always assumed it would be locked in the vault forever with the BASIC Stamp interpreters.
Looking promising but a guestimate here rather than every instruction confirmed - it's a real brain drainer doing this by hand !
000 : MOV $000,#5 count mov count,#5 ' How many words
001 : MOV $001,PAR ptr mov ptr,PAR ' Where from minus 2
002 : ADD $001,#2 Loop add ptr,#2 ' Point to first/next
003 : RDWORD $???,$001 LoopDst rdword ?,ptr ' Read word
004 : ADD $003,#$100 add LoopDst,#$100 ' Update dest
005 : ADD $003,#$100 add LoopDst,#$100
006 : DJNZ $000,#$002 djnz count,#Loop ' Repeat 5 times
007 : CALL #?
008 : MOV $000,$000
Not at all confident about 007 and onwards.
@ Chip : I don't think it's burn-out you should worry about, more damage to nations' entire economies while engrossed
I think we'd all hate to have the secret revealed if we thought we were on the verge of cracking it, but I don't think a "you're wildly off-track / have missed something major" would go amiss to save too much wasted time ( after a reasonable enough period to rescue ourselves ).
@ tpw_man : The hard part is getting the dump loop into the Cog running the interpreter and then getting it to run.
@ CJ : Maybe, but I cannot really imagine Chip having written code other than straight-forward, and the Interpreter doesn't really need to know how fast it's running.
The wrong turns are part of the fun. But please feel free to taunt us all you want!
I'm curious, though: why the sudden decision to release the interpreter code? I always assumed it would be locked in the vault forever with the BASIC Stamp interpreters.
-Phil
Well, if the code·CAN be extracted, I'd like to know about it sooner than later, because·I'd like to gauge· the effectiveness of this current scheme. Whether or not you guys crack this ROM, we are all learning some interesting things here. And there's nothing like experience to shatter or cement our convictions.
You guys are certainly exhibiting a lot·more intuition than I would·have, myself, or I would have imagined from others. So, it's confirmed to me that in a case like this, it takes a fractional amount of effort to design the obfuscation, compared to what it takes to reverse it. I'm also learning how an attacker might think, and that's very useful to know, as some simple, subtle departures from likelihood could really derail their efforts.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
Post Edited (Chip Gracey (Parallax)) : 2/22/2008 3:33:25 AM GMT
One summer I worked on a salmon troller in Alaska. The skipper was really fussy about how the food on board was handled. In particular, he had a rule about bread: never take the heel; always leave it on the end of the loaf. I made the comment: "So, we sacrifice the end piece and let it go stale to save the rest of the loaf?" "Yes," he replied, "and so it is in life." Shall I infer, then, that the Prop I interpreter code is merely the heel here and that the upcoming Prop II code is the next slice in the loaf?
I don't know if I am on the right track but the earlier code passes verification and I'm now partially automated !
If it is correct, I've identified 11 distinct bit mappings, but most importantly 4 of the 6 opcode bit mappings which has narrowed down each instruction to being one of four potentials.
The technique I'm using is to take the encrypted long and determine where each bit could not be in what I think the result is. By removing those from the list of possibilities, what's left are those bits which it could be, and when there's only one it could be the mapping is determined. I am surprised that just 5 unique opcodes revealed 35% of the total mapping, and 66% of the opcode mapping.
Unfortunately I've run into a design problem and need a code rewrite. I'm mapping encrypted bits to where they should be in the result, what I should be doing is setting each result bit from the encrypted bits. Even if a result bit could come from any number of encrypted bits, as long as all those are the same ( 1 or 0 ) the result bit is still known and that should provide a lot more information to guess at what each instruction is, maybe even fully reveal many.
I'm half expecting this to fall flat on its face at some point but it's looking good so far.
I'm in the middle of a new permutation analysis. I ran the floating point code through a frequency analysis (4 MSBs of i-field), and came up with the following (each mnemonic being the first in its 4-tuple):
One summer I worked on a salmon troller in Alaska. The skipper was really fussy about how the food on board was handled. In particular, he had a rule about bread: never take the heel; always leave it on the end of the loaf. I made the comment: "So, we sacrifice the end piece and let it go stale to save the rest of the loaf?" "Yes," he replied, "and so it is in life." Shall I infer, then, that the Prop I interpreter code is merely the heel here and that the upcoming Prop II code is the next slice in the loaf?
-Phil
I like that bread story, Phil. That guy sounds pretty wise. I was feeling pretty wise until about an hour ago, even talking like him.
It's now looking like my protection gizmo wasn't very effective, so I'll need to enhance it for the next Propeller.
Chip Gracey (Parallax) said...
I'm also learning how an attacker might think, and that's very useful to know, as some simple, subtle departures from likelihood could really derail their efforts.
If there were bit inversions, I'd probably throw in the towel. If bit-swapping or bit inversions were related to ROM address I almost certainly would. TBH, it's only because you revealed it was tending towards simplistic that I even gave it a go.
I have my towel ready in case I'm already entirely on the wrong track.
If there were a 'secret flag' in the Cog/Decoder set when CogInit activated and that enabled decryption for the interpreter load and returned garbage or zeroes when $F004-$FFFF were read otherwise ( by Spin or PASM ), we'd not have anything at all to even start with.
Comments
Assuming the tool Chip used sets src and dst to zero, all RET should have the same scrambled values except for any conditional execution part. Ignoring IF_NEVER, all RET instructions have between 6 and 9 bits set, the rest cleared, 9 bits set for an IF_ALWAYS RET.
Applying a bit-count puts a valid 'IF_ALWAYS RET' at 1E4, just before the constant which looks like -1 ... coincidence ? Or that -1 would be the first constant chosen to appear after code ?
On the counter-side, there are not as many scrambled longs which have the same value which suggests a lack of IF_ALWAYS RET, which seems unlikely.
Another target is IF_ALWAYS JMP #? which should have between 10 and 17 bits set. Any other instructions which should have a narrow band of bits set ?
Another interesting thing is that there are no zeroed longs in the Cog as one would expect for uninitialised variables ( zeroed longs exist in the loader part ). I suspect this is because run-time variables are overlaid on Cog Code once that has been executed and becomes redundant. The most obvious, executed and re-usable are at $000 up, so that may prove useful with src and dst registers mainly being zero bits elsewhere.
One final thought for now - Most of us are, in general, attacking the interpreter code; would a better approach be to attack the 'simpler' bootloader or even start with the constants loaded to the Cog ?
Checking one per second, that would take 8.3e+27 years to do brute force. Even getting the check down to milliseconds pre permutation won't practically help much.
It reminds me of the eternity puzzle. www.google.co.uk/search?q=eternity+puzzle&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US[noparse]:o[/noparse]fficial&client=firefox-a A jigsaw variant that offered £1,000,000 to the first person to solve it. The permutations were so huge that no foreseeable supercomputer could brute force the solution given millions of years. Yet the problem was understood and a way of whittling down the permutations was found which resulted in a solution being found by brute force in just a few months.
The key to that was one of parity. As I recall the pieces were conceptually made of several right angled triangles. Some left handed triangles, some right handed. So a given piece might have more right handed triangles in it, or more left handed pieces, or the same number. This gave a "parity" for each piece. It so happened that when a program was doing a search of permutations,, you could check the parity of the pieces you have left against the parity of the space left on the board to fill, and rule out a whole branch of the search tree.
Your suggestion of counting the number of ones and zeros in a long is parity too. If this is a bit swap situation, that does seem like a very promising angle to pursue.
I take that back. There was much talk of using parity to help solve eternity, but I've just read up the method that the winners used, and they didn't use parity, and suggest parity is useless for that puzzle. But that doesn't mean it won't be useful here.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Help to build the Propeller wiki - propeller.wikispaces.com
Play Defender - Propeller version of the classic game
Prop Room Robotics - my web store for Roomba spare parts in the UK
Post Edited (CardboardGuru) : 2/21/2008 2:46:27 PM GMT
That said, I don't think this "utility" can be based on static scrambling code; if it was then once you knew the trick all would be revealed. There has to be a key to make this work for the future and that key must be truly hidden in the scrambled image. I would think that with the "trick" understood you could find the key if you had both the source and scrambled images. Obviously you can extract the source if you have the scrambled and the key but cracking the scrambled without the key must be a serious effort even when you know the trick.
To make this a practical solution for the PropII you would need to prove that you coudn't find the key in someone's object based on numerous experiments where you have both the source and scrambled versions of your own code.
Have fun and I will continue to watch. I think the PropII will be well worth the wait.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
BioProp: Robotics - Powered by Bioloids and controlled by the Propeller
$000 : MOV $000,#5
$001 : MOV $001,PAR
There are the right number of bits in the first long and in the second for each of those instructions, plus the right number of changes ( bit sets and bit clears ) between the two. It's also what one would expect as there are five words which are in the info block the interpreter needs to use. Following should be some sort of copy/load from Hub code.
If correct, then it narrows down the potential bit swapping possibilities; one of three bits cleared maps to the I (immediate) bit, the other two to bits 0 and 2 (src), the six bits set map to bits 4 through 9 ( src, and lsb of dst ). The set and unchanged bits map to bit 29 and 31 (opc) and the other five to R and the four Condition bits.
Applying that to the constant at 1E8 would be interesting.
Post Edited (hippy) : 2/21/2008 4:08:01 PM GMT
I think you might be reading your ROM in big-endian form. You quoted the following data:
When I dump this section of ROM in LONG form, I get (with hub addresses):
Note that your 08000000 comes out 00000008.
As I've pointed out before, given the number of times certain longs are repeated, there's almost no chance that any kind of cumulative enciphering is afoot. This means that the same transformation is being applied to each long.
I've done some analysis on consecutive groups of 6 bits, using all possible rotations of the long and all possible 6-bit XOR patterns, in both forward and reverse order. What I was looking for was a reasonable instruction distribution (i.e. no MUL, MULS, ENC, or ONES; few, if any, WAITxx; lots of JMPRETs (same as JMPs)). So far, nothing stands out. Here's a sample of the program's output:
This, of course, is not a real candidate, since there are no hub instructions. Obviously, I need to hone my filter somewhat.
It's still possible that the target of a MOVI, for example, could be encoded as a MUL, say, to throw people off the scent. I would have to look at the bytecode list to determine if there's any correspondence between their bit patterns and those of the actual ASM instructions they represent. If so, a MOVI in the interpreter would make perfect sense. In any event, I suspect, as you do, that some bit-swapping/nybble-swapping/byte-swapping is taking place. It would be easiest to analyze if the swapping were local, but that 00000008 suggests otherwise and is what originally put me on the trail of rotations. The FFFFFFFF that precedes it suggests that there is no XORing taking place at all. So my next thrust will be looking at likely bit permutations.
-Phil
On your dump, don't forget that $F000-$F002 are part of the trig tables, and the Interpreter starts at $F004. I don't see any reason why the Cog wouldn't load 496 longs from $FFF4 onwards, thus no lsb-to-lsb mapping of ROM to Cog address ( for loader at $F800 there would be ). What's at 'unused' $F002..$F003; no idea ( is that the $02CA or $FFFF - unprogrammed ? )
I'm doing my decoding by hand based on counts of bits-set and guessing what the instruction could be. That at $003 could be a "MOV $003,#0", although there are other dst/src possibilities. If so it looks like bit 25 ( my endian ), bit 8 ( your endian ) is the I, immediate, bit. After that it gets more complicated; RDWORD, JMP, CALL ?
I've been working on how many bits are set or cleared compared with the suspected "MOV $000,#5" and which possible instruction those changes could give. That's still a lot of possibilities for each instruction, meaning scouring for changed-by-N bits instructions doesn't seem worthwhile yet. It is however possible to say what instructions something cannot be through too few bit changes. If the I bit mapping has been identified, that allows encrypted values of "MOV $000,#$000" and "MOV $000,$000" to be determined, a reasonable basis to base further bit-changes from.
Looking at where the bit changes are if it is as I've guessed for $000 and $001, it's 'random' bit swapping although some pattern could emerge. Handily consecutive bits, byte or nibble, unfortunately I don't think so.
Unfortunately, I haven't come up with a strategy for attempted decoding which can be automated yet.
I looked at Spin bytecode function to PASM opcode mappings which would make them easer to decode and handle using MOVI within the interpreter and I didn't see any obvious one-to-one mappings.
A peculiar thought occurred to me: Suppose part of the trig table, when interpreted as code, was actually able to write something to hub memory. One could then start a cog beginning in the trig table that would include part of the interpreter code. It would be a huge coincidence, but if just one or two longs from the interpreter code got written out to hub memory as a result, that could provide a huge clue as to how the bits are scrambled. Update: Never mind. There's nothing in the 512 longs preceding F004 that starts with 0 in the upper nybble.
Also, even though there are 32! bit permutations, one wouldn't have to examine nearly that many. For the i-field, there are "only" 32! / 26! possibilities -- still a large number, but accessible for exhaustive analysis on a fast computer. By partitioning opcodes into groups for frequency analysis, that number could be reduced even further. Once the opcode bits have been determined, any pattern extant in their selection might provide a clue for the other 26 bits.
-Phil
Post Edited (Phil Pilgrim (PhiPi)) : 2/21/2008 9:24:38 PM GMT
Then guessing a couple of instructions correctly ... quickly decreases the number of possible permutations,
and rapid successive approximation may happen as testing remaining permutations reveals more good instructions.
Another totally different idea:
Maybe the spin interpreter is a double interpreter,
so it squeezes more instructions in 496 longs.
Also, does the bootloader need all the memory reserved for it?
(Doesn't it have to be Spin bytecode to be able to run at all outside a cog? Maybe I missed something.)
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.
I assume, since you asked, that perhaps one of us has determined something. As much as I'd prefer not to know just yet what it might be, I'll happily defer to the majority, although it may have to wait until morning for Hippy in the UK. (I know you're just dying to tell us!)
-Phil
I've run some analyses over the latter space, hoping to find candidate permutations bearing some sort of pattern. My criteria were the following, relating to the number of instructions found:
····MUL group = 0
····WAIT group < 5
····MOVS group (includes JMPRET, JMP, RET) > 20
····MOV group > 20
····RDBYTE group > 20
····Any single group < 128
I found plenty of candidates, but no permutations bearing an obvious or simple pattern. Assuming that permutation is the sole obfuscation method used, this could be due to a couple factors:
1. Chip's chosen permutation employs a non-regular pattern.
2. There is data interspersed among the instructions that code into the MUL group, thereby disqualifying the permutation that produced them.
-Phil
IF_C_EQ_Z RDLONG $14C, #$001 WC
reading the global clock speed?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.
Should I quit with the psyops? Is it helping or hurting?
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
I am 1010, so be surprised!
IF_C_EQ_Z RDLONG $14C #$001 WC, reads the global clock speed
IF_Z HUBOP $0B8 #$01A WC NR , equates to a nop without Z set
then a rdlong of long 1 which includes the global clock register,
this is sounding like a good start for an interpreter that needs to know how fast it is going
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.
The wrong turns are part of the fun. But please feel free to taunt us all you want!
I'm curious, though: why the sudden decision to release the interpreter code? I always assumed it would be locked in the vault forever with the BASIC Stamp interpreters.
-Phil
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.
Not at all confident about 007 and onwards.
@ Chip : I don't think it's burn-out you should worry about, more damage to nations' entire economies while engrossed
I think we'd all hate to have the secret revealed if we thought we were on the verge of cracking it, but I don't think a "you're wildly off-track / have missed something major" would go amiss to save too much wasted time ( after a reasonable enough period to rescue ourselves ).
@ tpw_man : The hard part is getting the dump loop into the Cog running the interpreter and then getting it to run.
@ CJ : Maybe, but I cannot really imagine Chip having written code other than straight-forward, and the Interpreter doesn't really need to know how fast it's running.
Post Edited (hippy) : 2/22/2008 1:31:06 AM GMT
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Paul Baker
Propeller Applications Engineer
Parallax, Inc.
Anyway, the quest continues...
-Phil
You guys are certainly exhibiting a lot·more intuition than I would·have, myself, or I would have imagined from others. So, it's confirmed to me that in a case like this, it takes a fractional amount of effort to design the obfuscation, compared to what it takes to reverse it. I'm also learning how an attacker might think, and that's very useful to know, as some simple, subtle departures from likelihood could really derail their efforts.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
Post Edited (Chip Gracey (Parallax)) : 2/22/2008 3:33:25 AM GMT
Ah, so. This is all about the Prop II, isn't it?
One summer I worked on a salmon troller in Alaska. The skipper was really fussy about how the food on board was handled. In particular, he had a rule about bread: never take the heel; always leave it on the end of the loaf. I made the comment: "So, we sacrifice the end piece and let it go stale to save the rest of the loaf?" "Yes," he replied, "and so it is in life." Shall I infer, then, that the Prop I interpreter code is merely the heel here and that the upcoming Prop II code is the next slice in the loaf?
-Phil
If it is correct, I've identified 11 distinct bit mappings, but most importantly 4 of the 6 opcode bit mappings which has narrowed down each instruction to being one of four potentials.
The technique I'm using is to take the encrypted long and determine where each bit could not be in what I think the result is. By removing those from the list of possibilities, what's left are those bits which it could be, and when there's only one it could be the mapping is determined. I am surprised that just 5 unique opcodes revealed 35% of the total mapping, and 66% of the opcode mapping.
Unfortunately I've run into a design problem and need a code rewrite. I'm mapping encrypted bits to where they should be in the result, what I should be doing is setting each result bit from the encrypted bits. Even if a result bit could come from any number of encrypted bits, as long as all those are the same ( 1 or 0 ) the result bit is still known and that should provide a lot more information to guess at what each instruction is, maybe even fully reveal many.
I'm half expecting this to fall flat on its face at some point but it's looking good so far.
Bit mappings I think there are so far ...
You're still up? It's after four a.m. there!
I'm in the middle of a new permutation analysis. I ran the floating point code through a frequency analysis (4 MSBs of i-field), and came up with the following (each mnemonic being the first in its 4-tuple):
movs: 38.6% mov: 23.6% and: 9.9% add: 9.3% ror: 7.9% wrbyte: 2.0% rcr: 1.8% cmps: 1.3% mins: 1.1% cmpsub: 0.9% negc: 0.7% sumc: 0.2%This changes my acceptance filter considerably, although the FP code may be peculiar as far as frequencies go...
-Phil
It's now looking like my protection gizmo wasn't very effective, so I'll need to enhance it for the next Propeller.
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Chip Gracey
Parallax, Inc.
If there were bit inversions, I'd probably throw in the towel. If bit-swapping or bit inversions were related to ROM address I almost certainly would. TBH, it's only because you revealed it was tending towards simplistic that I even gave it a go.
I have my towel ready in case I'm already entirely on the wrong track.
If there were a 'secret flag' in the Cog/Decoder set when CogInit activated and that enabled decryption for the interpreter load and returned garbage or zeroes when $F004-$FFFF were read otherwise ( by Spin or PASM ), we'd not have anything at all to even start with.